The background of the invention will be discussed in two parts.
1. Field of the Invention
This invention relates to digital image processing, and more particularly to a convolution processor for digital image processing.
2. Description of the Prior Art
Modern technology utilizes all types of pictures, or images, as sources of information for interpretation and analysis. While some interpretation and analysis can be done by visual or optical means, a greater volume can be performed much faster and more accurately through use of a high speed computer. This requires that the image, in whatever original form, be placed in a digital form suitable for processing to obtain the desired analysis. Once digitized, the data representative of the image may be readily processed electronically to perform a number of different operations on the data, for providing another image, stressing certain aspects of the original image which has been operated upon. Typical digital image processing operations include image enhancement, such as when the original image is lacking in definition due to focusing problems, or the like; contrast enhancement, in which the digitally created image provides greater contrast, or brightness differences, between adjacent objects of the original image; or edge enhancement, in which the edges surrounding the various objects and features of the original image are stressed in the created image.
The typical original image, in most instances, is a "black and white" image; that is, for example, a photograph having black, white and varying shades of gray, which collectively depict an image. Color images may likewise be processed, although the digital data requirements are obviously different, if data indicative of color is included. Other examples of digital image processing may include images out of the visible region, such as infrared and radar images, in which the original image may be a digital image which is suitably processed to reduce noise, for example.
In any event, it is ultimately desired to display an image on a display screen, or in some other visible form, with the ultimate or created image having, for example, the contrast enhanced, the edges enhanced, or the noise removed, or substantially reduced. Furthermore, the processed image may also be used in higher level computational processors, and need not necessarily be viewed. Digital image processing is generally accomplished on a point by point, or pixel by pixel, basis; that is, each pixel of the original image, in digital form, is evaluated, interpreted, analyzed and processed in accordance with a predetermined method intended to accomplish the ultimate objective on the created image.
Since pixels of an original image may be readily identified on a coordinate basis, that is on an X-axis, Y-axis coordinate reference with respect to the matrix of pixels in the image, the original digital data generally takes the form of information relating to the X, Y position and a digital number representative of some characteristic or attribute of the gray level of the particular pixel, with values of 0 to 255 typically being assigned for gray shades where 0 is black and 255 is white. A pixel matrix for a display may be, for example, 512 by 512, that is 262,144 pixels on the display. Other matrix arrangements may be used, such as 640 columns by 480 rows, or any other arrangement. In some processes, where a video display is used, X, Y coordinate information is not required, and pixel positions may be designated or located relative to an event, such as positions following a retrace signal. In any event, in a typical image processing system, digital data representing each pixel is stored in a source image memory from which it can be computationally adjusted, pixel by pixel, for transfer to a destination image memory, which stores the adjusted result, usually in the same spatial orientation as the original image. The results so stored may be further modified until the completion of the manipulation to produce the ultimate processed image on a display. Since the process frequently involves a display, the computations are often conveniently performed at raster scan rates and in a format consistent with raster scan display.
For digital image processing, depending on the particular end objective, such as edge enhancement, noise reduction, etc., the data representing each pixel may be digitally manipulated by multiplication, addition, subtraction and the like, to place the original data from the source memory into an adjusted format in the destination memory for accomplishing the ultimate objective. In some other systems of image processing by use of digitally represented pixel information, certain non-linear mathematical processing is performed on the data base for image enhancement, or extraction of data of particular significance. For many commonly used enhancement purposes, each pixel of the enhanced image, hereinafter called the "enhanced object pixel", is extracted from an area of the original image involving that pixel of the original image, hereinafter called the "source object pixel", and each of the neighboring pixels surrounding it, that is in both the +/- X-axis and +/- Y-axis directions. For this purpose, again determined by the end objective, a "kernel" may be utilized, with the kernel being a computational array of coefficients or values best intended to accomplish the end result. These coefficients are arithmetically applied to gray level values of the object pixel and its neighbors. A 3.times.3 kernel may be used, for example, having three rows and three columns of assigned values, that is, nine values. Other kernels may be employed, for example, 5.times.5 or 21.times.21. Commencing at a given pixel location, for example, the first row and first column, the processing to obtain the modified value for each enhanced object pixel involves mathematical manipulation or adjustment of the data representative of each source object pixel and its eight surrounding neighbors, by nine respective assigned kernel values (in the case of a 3.times.3 kernel). Interim results are obtained, which may be further processed to obtain final results, which are suitably displayed or stored, and, in effect, are the processed image desired. This process is referred to as spatial filtering, image convolving or image convolution.
For one particular method of image convolution, in a typical prior art hardware mechanization, the system utilizes a "brute force" method of an array of multipliers and adders, operating in parallel on each row and column of pixels. To convolve an image having a pixel array with dimensions I by J, and with a convolution kernel having dimensions M by N requires I.times.J.times.M.times.N multiplications and additions. Typically, I and J are 512, and M and N are 3, requiring 512.times.512.times.3.times.3, or approximately 2,360,000 multiplies and adds. In such a typical hardware implementation, with a 3.times.3 kernel, this is conventionally accomplished with 9 multipliers, 9 adders and 3 line buffers, and performs the convolution in one raster frame time. Once implemented for a particular kernel size and shape, the hardware is set to that M.times.N kernel, and cannot be readily reconfigured for other sizes and shapes of kernels.
A hardware intensive approach to digital image processing is exemplified by U.S. Pat. No. 4,464,788, issued to Sternberg, et al on Aug. 7, 1984, such patent being entitled "Dynamic Data Correction for an Image Analyzer System". At the other end of the spectrum are those systems which are software intensive, which provide a high degree of flexibility with an inherent lack of speed. One such image processing system utilizing digital filtering techniques is shown and described in U.S. Pat. No. 4,330,833, issued May 18, 1982 to Pratt et al., such patent being entitled "Method and Apparatus for Improved Digital Image Processing".
On the one hand, hardware implementation, while obviously high speed, has a corresponding lack of economy and flexibility. Moreover, a change in the kernel size and shape cannot be readily accomplished, particularly if a desired kernel structure falls outside the matrix of the original kernel for which the hardware was configured. On the other hand, intensive software implementation has high flexibility and economy, while suffering from slow speed, particularly where a kernel size and shape is complex.